//给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
//你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
//返回滑动窗口中的最大值 。

//示例 1：
//输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//输出：[3,3,5,5,6,7]
//解释：
//滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3
//1 [3  -1  -3] 5  3  6  7       3
//1  3 [-1  -3  5] 3  6  7       5
//1  3  -1 [-3  5  3] 6  7       5
//1  3  -1  -3 [5  3  6] 7       6
//1  3  -1  -3  5 [3  6  7]      7
//示例 2：
//输入：nums = [1], k = 1
//输出：[1]

//提示：
//1 <= nums.length <= 105
//-104 <= nums[i] <= 104
//1 <= k <= nums.length

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

class Solution {
public:
    // 使用带排序的数据结构set来实现弹出、弹入以及寻找最大值
    // 时间复杂度 o((n-k)*k)
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> queue{};
        int max_num = 0;
        int max_time = 1; //记录数据结构中，最大值数的个数

        for (int i=0; i<k; ++i){
            queue.push_back(nums[i]);
        }

        int len = nums.size();
        find_max_time(queue, max_num, max_time);
        ans.push_back(max_num);
        for(int i=k; i<len; ++i){
            queue.push_back(nums[i]);
            int pop_num = queue.front();
            queue.pop_front();

            if (pop_num == max_num){
                if(nums[i]>max_num){
                    max_num = nums[i];
                    max_time = 1;
                }else if (nums[i] == max_num){
                    ;
                } else{
                    if (max_time >1){
                        --max_time;
                    } else{
                        find_max_time(queue, max_num, max_time);
                    }
                }

            }else{
                if(nums[i]>max_num){
                    max_num = nums[i];
                    max_time = 1;
                } else if (nums[i] == max_num){
                    ++max_time;
                }
            }
            ans.push_back(max_num);
        }

        return ans;
    }

    void find_max_time(deque<int> & queue, int& max, int & time){
        max = queue.front();
        int n = queue.size();
        for(int i=1; i<n; ++i){
            if (queue[i] > max){
                max = queue[i];
                time = 1;
            } else if (queue[i] == max) {
                ++time;
            }
        }
    }
};

int main() {
//    vector<int> nums = {1,3,-1,-3,5,3,6,7}; int k = 3;
    vector<int> nums = {-7,-8,7,5,7,1,6,0}; int k = 4;
    Solution sol;
    auto ans = sol.maxSlidingWindow(nums, k);
    for(auto item: ans){
        cout<< item <<" ";
    }
    cout<<endl;

    return 0;
}


//// 使用带排序的数据结构set来实现弹出、弹入以及寻找最大值
//// 时间复杂度 o((n-k)*k)
//// 539 ms
//vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//    vector<int> ans;
//    auto l=nums.begin(), r = nums.begin()+k;
//    multiset<int> num_set(l, r);
//
//    while(r != nums.end()){
//        auto it = prev(num_set.end());
//        ans.push_back(*it);
//
//        it = num_set.find(*l);
//        num_set.erase(it);
//        num_set.insert(*r);
//        ++l; ++r;
//    }
//    auto it = prev(num_set.end());
//    ans.push_back(*it);
//
//    return ans;
//}

//// 手动维护列表最大值，在哪怕考虑了入栈和出栈的数字的大小与列表中最大值的大小，仍然超时
//vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//    vector<int> ans;
//    deque<int> queue{};
//    int max_num = 0;
//    int max_time = 1; //记录数据结构中，最大值数的个数
//
//    for (int i=0; i<k; ++i){
//        queue.push_back(nums[i]);
//    }
//
//    int len = nums.size();
//    find_max_time(queue, max_num, max_time);
//    ans.push_back(max_num);
//    for(int i=k; i<len; ++i){
//        queue.push_back(nums[i]);
//        int pop_num = queue.front();
//        queue.pop_front();
//
//        if (pop_num == max_num){
//            if(nums[i]>max_num){
//                max_num = nums[i];
//                max_time = 1;
//            }else if (nums[i] == max_num){
//                ;
//            } else{
//                if (max_time >1){
//                    --max_time;
//                } else{
//                    find_max_time(queue, max_num, max_time);
//                }
//            }
//
//        }else{
//            if(nums[i]>max_num){
//                max_num = nums[i];
//                max_time = 1;
//            } else if (nums[i] == max_num){
//                ++max_time;
//            }
//        }
//        ans.push_back(max_num);
//    }
//
//    return ans;
//}
//void find_max_time(deque<int> & queue, int& max, int & time){
//    max = queue.front();
//    int n = queue.size();
//    for(int i=1; i<n; ++i){
//        if (queue[i] > max){
//            max = queue[i];
//            time = 1;
//        } else if (queue[i] == max) {
//            ++time;
//        }
//    }
//}